﻿////////////////////////////////////////////////////////////////////////
// RDirNode
////////////////////////////////////////////////////////////////////////

/**
* RDirNode implements directory (intermediate) nodes in the R*-tree

* the block of the STSDirNode is organized as follows:
* +--------+-------------+-------------+-----+----------------------+
* | header | STSDirEntry[0] | STSDirEntry[1] | ... | STSDirEntry[capacity-1] |
* +--------+-------------+-------------+-----+----------------------+

* the header of the STSDirNode is organized as follows:
* +-------------+-------+-------------+
* | hasDataSon | level | noEntries |
* +-------------+-------+-------------+
*/

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using TSTreeSAX.fuctions;

namespace TSTreeSAX
{
  public  class STSDirNode : STSNode,INode
    {
        public STSDirEntry[] entries;            // array of entries in the directory
        public bool hasDataSon;           // true, if son is a data page


        // create a brand new directory node
        public STSDirNode(STRTree rt, int length)
            : base(rt, length)
        {

            byte[] b;
            int headerSize;
            STSDirEntry d;

            d = new STSDirEntry(dimension, hasDataSon, rt,length);

            headerSize = Constants.SIZEOF_Boolean   //hasDataSon
                       + Constants.SIZEOF_SHORT //level
                       + Constants.SIZEOF_INT;  //noEntries
            capacity = (rt.file.getBlocklength() - headerSize) / d.getSize();
            //Console.WriteLine("STSDirNode created. Id: " + rt.noOfInternalNode);
          // Console.WriteLine("STSDirNode capacity " + capacity);

            entries = new STSDirEntry[capacity];

            b = new byte[rt.file.getBlocklength()];
            // append block to the rtree's blockfile
            try
            {
                block = rt.file.appendBlock(b);
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
                Utilities.processError("STSDirNode creation: error in block appending", true);
            }

            rt.noOfInternalNode++;
            dirty = true;
        }
        // this constructor reads an existing STSDirNode from the disk
        public STSDirNode(STRTree rt, int _block, int length)
            : base(rt,length)
        {
            byte[] b;
            int header_size;
            STSDirEntry d;

            d = new STSDirEntry(dimension, hasDataSon, rt,length);
            header_size = Constants.SIZEOF_Boolean   //hasDataSon
                            + Constants.SIZEOF_SHORT //level
                            + Constants.SIZEOF_INT;  //noEntries
            capacity = (rt.file.getBlocklength() - header_size) / d.getSize();

            //Console.WriteLine("STSDirNode created. Id: " + rt.noOfInternalNode);
           // Console.WriteLine("STSDirNode capacity " + capacity);

            //STSDirNode__dimension = dimension;
            //STSDirNode__myTree = myTree;
            entries = new STSDirEntry[capacity];

            block = _block;
            b = new byte[rt.file.getBlocklength()];
            // this time we read the directory node block from the disk
            try
            {
                rt.file.readBlock(b, block);
                readFromBuffer(b);
            }
            catch (Exception e)
            {
                Utilities.processError("STSDirNode initialization: error in block reading" + e.ToString(), true);
            }

            dirty = false;
        }
        public bool isDataNode()  // this is a directory node
        {
            return false;
        }

        // transform the sequential block information in buffer to object information
        public void readFromBuffer(byte[] buffer)
        {
            MemoryStream byteIn = new MemoryStream(buffer);
            BinaryReader binReader = new BinaryReader(byteIn);

            // read header info
            hasDataSon = binReader.ReadBoolean();
            level = binReader.ReadInt16();
            noEntries = binReader.ReadInt32();

            //Console.WriteLine("STSDirNode.read_from_buffer(): noEntries =" +noEntries);

            // read directory entries
            for (int i = 0; i < noEntries; i++)
            {
                entries[i] = new STSDirEntry(dimension, hasDataSon, myTree,length);
                entries[i].readFromBuffer(binReader);
                entries[i].sonIsData = hasDataSon;
            }

            binReader.Close();
            byteIn.Close();
        }
        // serialize the object's information to the buffer[]
        public void writeToBuffer(byte[] buffer)
        {
            MemoryStream byteOut = new MemoryStream(buffer.Length);
            BinaryWriter binWriter = new BinaryWriter(byteOut);

            // write header info
            binWriter.Write(hasDataSon);
            binWriter.Write(level);
            binWriter.Write(noEntries);

            // write directory entries
            for (int i = 0; i < noEntries; i++)
                entries[i].writeToBuffer(binWriter);

            //byte[] bytes = new byte[myTree.file.getBlocklength()];
            //bytes = byte_out.toByteArray();
            byte[] bytes = byteOut.ToArray();


            int bl = bytes.Length;
            for (int i = 0; i < bytes.Length; ++i)
                buffer[i] = bytes[i];

            binWriter.Close();
            byteOut.Close();
        }

        // prints the mbrs of all directory entries in this node
        public void print()
        {
            int i, n;

            n = getNoEntries();
            for (i = 0; i < n; i++)
            {
                Console.WriteLine(entries[i].bounces[0]
                                    + " " + entries[i].bounces[1]
                                    + " " + entries[i].bounces[2]
                                    + " " + entries[i].bounces[3]);
            }
            Console.WriteLine("level: " + level);
        }
        /*
        * recursive call to compute the # of data in the tree
        */
        public int getNoOfData()
        {
            int i, n, sum;

            n = getNoEntries();
            sum = 0;
            for (i = 0; i < n; i++)
                sum += entries[i].noOfData;
            return sum;
        }
        public char[] getMBR()
        {
            int i, j, n;
            char[] mbr;

            mbr = new char[2 * dimension];
            for (i = 0; i < 2 * dimension; i++)
                mbr[i] = entries[0].bounces[i];

            n = getNoEntries();
            for (j = 1; j < n; j++)
            {
                for (i = 0; i < 2 * dimension; i += 2)
                {
                    mbr[i] = mbr[i] < entries[j].bounces[i] ? mbr[i] : entries[j].bounces[i];// Math.Min(mbr[i], entries[j].bounces[i]);
                    mbr[i + 1] = mbr[i + 1] > entries[j].bounces[i + 1] ? mbr[i + 1] : entries[j].bounces[i + 1];// Math.Max(mbr[i + 1], entries[j].bounces[i + 1]);
                }
            }
            return mbr;
        }

        public char[] getSep(char[] left, char[] right)
        {
            char[] sep;
            sep = new char[dimension];
            for (int i = 0; i < 2 * dimension; i += 2)
            {
                if (left[i + 1] < right[i])
                {
                    sep[i/2] = right[i];
                    return sep;
                }
                else if (left[i + 1] == right[i])
                {
                    sep[i/2] = right[i];
                }
                else if (left[i + 1] > right[i])
                {
                    sep[i/2] = left[i + 1];
                }
            }
            return sep;
        }
        /*
         * insert an entry into the node
        * it should be called only for not full nodes
        */
        public void insertEntry(STSDirEntry de)
        {
            if (getNoEntries() > (capacity - 1))
                Utilities.processError("STSDirNode.insertEntry: called, but node is full", true);

            entries[noEntries] = de;
            noEntries++;
        }
        /*
    * split this to this and the new node brother
    * called when the node overflows and a split has to take place.
    * invokes STSNode.split() to calculate the split distribution
    */


        /**
        * chooses the best subtree under this node to insert a new mbr
        * There are three cases:
        * Case 1: the new mbr is contained (inside) in only one directory entry mbr.
        * In this case follow this subtree.
        * Case 2: the new mbr is contained (inside) in more than one directory entry mbr.
        * In this case follow the entry whose mbr has the minimum area
        * Case 3: the new mbr is not contained (inside) in any directory entry mbr
        * In this case the criteria are the following:
        * - If the son nodes are data nodes consider as criterion first the minimum overlap
        *   increase if we follow one node with its neighbors, then the minimum area enlargement
        *   and finally the minimum area
        * - In the son nodes are dir nodes consider as criterion first the minimum area enlargement
        *   and finally the minimum area
        * After we choose the subtree, we enlarge the directory entry (if has to be enlarged)
        * Return the index of subtree
        */
        public int chooseSubtree(char[] point)
        {
            int i, j, n, follow, minindex = 0, inside_count;
            int[] inside;
            char[] bmbr = new char[2 * dimension];
            float old_o, o, omin, a, amin, f, fmin;
           // char[] mbr;

            n = getNoEntries();

            // d in doubt an existing entry ?
            inside_count = 0;   // this variable holds the number of entries whose mbr contains the new mbr to be inserted
            inside = new int[n]; // this array holds the indices of entries whose mbr contains the new mbr to be inserted

            // calculate inside[]

            //mbr = new char[dimension * 2];

            //for (i = 0; i < dimension * 2; i += 2)
            //{
            //    mbr[i] = point[i / 2];
            //    mbr[i + 1] = point[i / 2];
            //}

            float mindist = entries[0].minDist(point);
            inside[inside_count] = 0;
            inside_count++;

            for (i = 1; i < n; i++)
            {
                if (entries[i].minDist(point) < mindist)
                {
                    mindist = entries[i].minDist(point);

                    Array.Clear(inside, 0, inside.Length);
                    inside_count = 0;

                    inside[inside_count] = i;
                    inside_count++;
                }
                else if (entries[i].minDist(point) == mindist)
                {
                    inside[inside_count] = i;
                    inside_count++;
                }
            }

            //for (i = 0; i < n; i++)
            //{
            //    switch (entries[i].interSection(mbr))
            //    {
            //        case Constants.INSIDE:
            //            // mbr is inside entries[i] mbr
            //            inside[inside_count++] = i;
            //            break;
            //    }
            //}

            if (inside_count == 1)
                // Case 1: There is exactly one dir_mbr that contains mbr
                follow = inside[0];
            else //if (inside_count > 1)
            // Case 2: There are many dir_mbrs that contain mbr
            // choose the one for which insertion causes the minimum area enlargement
            {
                fmin = Utilities.computeArea(dimension, entries[inside[0]].bounces, length); // Constants.MAXREAL;
                minindex = 0;
                for (i = 1; i < inside_count; i++)
                {
                    f = Utilities.computeArea(dimension, entries[inside[i]].bounces, length);
                    if (f <= fmin)
                    {
                        minindex = i;
                        fmin = f;
                    }
                }

                follow = inside[minindex];
            }
            //else
            //// Case 3: There are no dir_mbrs that contain mbr
            //// choose the one for which insertion causes the minimum overlap if hasDataSon
            //// else choose the one for which insertion causes the minimum area enlargement
            //{
            //    if (hasDataSon)
            //    {
            //        omin = Constants.MAXREAL;
            //        fmin = Constants.MAXREAL;
            //        amin = Constants.MAXREAL;
            //        for (i = 0; i < n; i++)
            //        {
            //            // compute the MBR of mbr and entries[i]

            //            Utilities.enlargeMBR(dimension, bmbr, mbr, entries[i].bounces);

            //            // calculate area and area enlargement
            //            a = Utilities.computeArea(dimension, entries[i].bounces, length);
            //            f = Utilities.computeArea(dimension, bmbr, length) - a;

            //            // calculate overlap before enlarging entry i th
            //            old_o = o = (float)0.0;

            //            for (j = 0; j < n; j++)
            //            {
            //                if (j != i)
            //                {
            //                    old_o += Utilities.calcOverlapArea(dimension, entries[i].bounces, entries[j].bounces, length);
            //                    o += Utilities.calcOverlapArea(dimension, bmbr, entries[j].bounces, length);
            //                }
            //            }
            //            o -= old_o;

            //            // is this entry better than the former optimum ?
            //            if ((o < omin) ||
            //                (o == omin && f < fmin) ||
            //                (o == omin && f == fmin && a < amin))
            //            {
            //                minindex = i;
            //                omin = o;
            //                fmin = f;
            //                amin = a;
            //            }
            //            //delete [] bmbr;
            //        }
            //    }
            //    else //son is not data
            //    {
            //        fmin = Constants.MAXREAL;
            //        amin = Constants.MAXREAL;
            //        for (i = 0; i < n; i++)
            //        {
            //            // compute the MBR of mbr and entries[i]
            //            Utilities.enlargeMBR(dimension, bmbr, mbr, entries[i].bounces);

            //            // calculate area and area enlargement
            //            a = Utilities.computeArea(dimension, entries[i].bounces, length);
            //            f = Utilities.computeArea(dimension, bmbr, length) - a;

            //            // is this entry better than the former optimum ?
            //            if ((f < fmin) || (f == fmin && a < amin))
            //            {
            //                minindex = i;
            //                fmin = f;
            //                amin = a;
            //            }
            //            //delete [] bmbr;
            //        }
            //    }
            //    // enlarge the boundaries of the directory entry we will follow

            //    Utilities.enlargeMBR(dimension, bmbr, mbr, entries[minindex].bounces);
            //    for (i = 0; i < 2 * dimension; i++)
            //    {
            //        entries[minindex].bounces[i] = bmbr[i];

            //    }
            //    follow = minindex;

            //    // nod has changed; set the dirty bit
            //    dirty = true;

            //}

            //Console.WriteLine(follow.ToString());

            return follow;
        }
        /*
        * split this to this and the new node brother
        * called when the node overflows and a split has to take place.
        * invokes STSNode.split() to calculate the split distribution
        */
        public void split(STSDirNode brother)
        // 	splits the current node so that m mbr's to be moved sn
        {
            int i, dist, n;
            int[][] distribution;                    // distribution[0] will hold the best split distribution order
            char[][] mbr_array;                     // array of the mbrs of all entries
            STSDirEntry[] new_entries1, new_entries2; // the new directory entries that will hold the split parts


            // because how many are now occupied?
            n = getNoEntries(); // n = number of directory entries
            distribution = new int[1][];

            // mbr_array holds the mbrs of all entries
            mbr_array = new char[n][];
            for (i = 0; i < n; i++)
                mbr_array[i] = new char[2 * dimension];

            for (i = 0; i < n; i++)
                mbr_array[i] = entries[i].bounces;

            // call super.split() to initialize distribution[0], dist
            dist = base.split(mbr_array, distribution);

            // generate new data Array 
            // -. see constructor
            //STSDirNode__dimension = dimension;
            //STSDirNode__myTree = myTree;

            //initialize the new entries that will hold the split parts
            new_entries1 = new STSDirEntry[capacity];
            new_entries2 = new STSDirEntry[capacity];

            // fill the new entries with the split parts
            for (i = 0; i < dist; i++)
            {
                new_entries1[i] = entries[distribution[0][i]];
            }

            for (i = dist; i < n; i++)
            {
                new_entries2[i - dist] = entries[distribution[0][i]];
            }

            // Share data arrays
            // As the successor nodes but not to be deleted
            // Before the call to delete all the pointers to zero
            //for (i = 0; i < n; i++)
            //{
            //       entries[i].son_ptr = null;
            //       brother.entries[i].son_ptr = null;
            //}

            // update this' and the brother's entries after the split
            entries = new_entries1;
            brother.entries = new_entries2;

            // Number of posts correct
            noEntries = dist;
            brother.noEntries = n - dist;  // must remain so because of rounding!
        }

        /*
        * insert a new data under this node
        * this function may cause the directory node to split
        * NOTE: the parameter sn is a reference call to sn[0] which will be
        * a new node after a potential split and NOT an array of nodes
        */
        public int insert(STSData d, STSNode[] sn)
        {
            int follow;
            STSNode succ = null;
            STSNode[] new_succ = new STSNode[1];
            STSDirEntry de;
            int ret;
            char[] mbr, nmbr, leftsep, nleftsep, rightsep, nrightsep;

            // choose subtree to follow
            mbr = d.getMBR();
            follow = chooseSubtree(mbr);

            // follow = chooseSubtree(d.point);
            // get corresponding son
            succ = entries[follow].getSon();

            // insert d into son
            ret = ((INode)succ).insert(d, new_succ);
            if (ret != Constants.NONE)
            // if anything (SPLIT or REINSERT) happened -. update bounces of entry "follow"
            // because these actions change the entries in succ
            {
                //update bounces
                mbr = ((INode)succ).getMBR();
                for (int i = 0; i < 2 * dimension; i++)
                    entries[follow].bounces[i] = mbr[i];
                // update separators
                Array.Clear(entries[follow].rightsep, 0, entries[follow].rightsep.Length);
                Array.Clear(entries[follow].leftsep, 0, entries[follow].leftsep.Length);

                if (follow == 0)
                {
                    rightsep = getSep(entries[follow].bounces, entries[follow + 1].bounces);
                    //for (int i = 0; i < dimension; i++)
                    //    entries[follow].rightsep[i] = rightsep[i];
                    for (int i = 0; i < dimension; i++) 
                    {
                        entries[follow].rightsep[i] = rightsep[i];
                        
                    }
                    entries[follow].leftsep[0] = entries[follow].bounces[0];
                }
                else if (follow == getNoEntries() - 1)
                {
                    leftsep = getSep(entries[follow - 1].bounces, entries[follow].bounces);
                    
                    for (int i = 0; i < dimension; i ++) 
                    {
                        entries[follow].leftsep[i] = leftsep[i];
                       
                    }
                    entries[follow].rightsep[0] = entries[follow].bounces[1];
                }
                else 
                { 
                    leftsep = getSep(entries[follow - 1].bounces, entries[follow].bounces);
                    rightsep = getSep(entries[follow].bounces, entries[follow + 1].bounces);
                   

                    for (int i = 0; i < dimension; i++) {
                        entries[follow].leftsep[i] = leftsep[i];
                        entries[follow].rightsep[i] = rightsep[i];
                    }
                }
                // System.arraycopy(mbr, 0, entries[follow].bounces, 0, 2 * dimension);
            }

            // recalculate # of succeeder in the tree
            entries[follow].noOfData = ((INode)succ).getNoOfData();

            if (ret == Constants.SPLIT)
            // succ was split into succ and new_succ[0]
            {
                // some error checking
                if (getNoEntries() == capacity)
                    Utilities.processError("STSDirNode.insert: maximum capacity violation", true);

                // create a new entry to hold the new_succ[0] node 
                de = new STSDirEntry(dimension, hasDataSon, myTree,length);
                nmbr = ((INode)new_succ[0]).getMBR();
                for (int i = 0; i < 2 * dimension; i++)
                {
                    de.bounces[i] = nmbr[i];
                    //System.arraycopy(nmbr, 0, de.bounces, 0, 2*dimension);
                }
                // add separators
                nleftsep = getSep(entries[noEntries - 1].bounces, de.bounces);
               
                // right separators = upper bounces of new entry
                Array.Clear(de.rightsep, 0, de.rightsep.Length);
                Array.Clear(de.leftsep, 0, de.leftsep.Length);

                de.rightsep[0] = de.bounces[1];
                for (int i = 0; i < 2 * dimension; i+=2)
                {
                    de.leftsep[i/2] = nleftsep[i/2];
                }

                de.son = new_succ[0].block;
                de.sonPtr = new_succ[0];
                de.sonIsData = hasDataSon;
                de.noOfData = ((INode)new_succ[0]).getNoOfData();

                // insert de to this
                insertEntry(de);

                if (getNoEntries() == (capacity - 1))
                // directory node overflows -. Split
                // this happens already if the node is nearly filled (capacity - 1)
                // for the algorithms are more easy then
                {
                    // initialize brother(split) node
                    sn[0] = new STSDirNode(myTree, length);
                    ((STSDirNode)sn[0]).hasDataSon = ((STSDirNode)this).hasDataSon;
                    sn[0].level = level;
                    // split this --> this and sn[0]
                    split((STSDirNode)sn[0]);

                    ret = Constants.SPLIT;
                }
                else
                    ret = Constants.NONE;
            }
            // must write page. set dirty bit
            dirty = true;

            return ret;
        }

        public STSData get(int i)
        {
            int j, n, sum;
            STSNode son;

            n = getNoEntries();
            sum = 0;
            for (j = 0; j < n; j++)
            {
                sum += entries[j].noOfData;

                if (sum > i)
                // i-th object is behind this node -. follow son
                {
                    son = entries[j].getSon();
                    return ((INode)son).get(i - (sum - entries[j].noOfData));
                }
            }

            return null;
        }

        /*
        * print the mbrs under this node that intersect the query mbr
        */
        public void region(char[] mbr)
        {
            int i, n;
            int s;
            STSNode succ;

            n = getNoEntries();
            for (i = 0; i < n; i++)
            {
                s = entries[i].interSection(mbr);
                if (s == Constants.INSIDE || s == Constants.OVERLAP)
                {

                    succ = entries[i].getSon();
                    ((INode)succ).region(mbr);
                }
            }
        }

        /*
        * print the mbrs under this node that intersect the query point
        */
        public void pointQuery(char[] p)
        {
            int i, n;
            STSNode succ;

            n = getNoEntries();
            for (i = 0; i < n; i++)
            {
                if (entries[i].isInside(p))
                {
                    succ = entries[i].getSon();
                    ((INode)succ).pointQuery(p);
                }
            }
        }

        /*
        * store in res the mbrs under this node that intersect the query point
        */
        public void pointQuery(STSPoint p, SortedLinList res)
        {
            int i, n;
            STSNode succ;

            //page_access += myTree.node_weight[level];
            myTree.page_access++;

            n = getNoEntries();
            for (i = 0; i < n; i++)
            {
                if (entries[i].isInside(p.data))
                {
                    succ = entries[i].getSon();
                    ((INode)succ).pointQuery(p, res);
                }
            }
        }

        /*
        * store in res the mbrs under this node that intersect the query mbr
        */
        public void rangeQuery(char[] mbr, SortedLinList res)
        {
            int i, n;
            int s;
            STSNode succ;

            //page_access += myTree.node_weight[level];
            myTree.page_access++;

            n = getNoEntries();
            for (i = 0; i < n; i++)
            {
                s = entries[i].interSection(mbr);
                if (s == Constants.INSIDE || s == Constants.OVERLAP)
                {
                    succ = entries[i].getSon();
                    ((INode)succ).rangeQuery(mbr, res);
                }
            }
        }

        /*
        * store in res the mbrs under this node that intersect the query circle
        */
        public void rangeQuery(STSPoint center, float radius, SortedLinList res)
        {
            int i, n;
           // Boolean s;
            STSNode succ;
            //int[] search;
            //int search_count = 0;

            /////////////////////////////////////////////////////
            myTree.page_access++;
            myTree.index_acess++;

            //byte[] block = new byte[myTree.file.getBlocklength()];
            //myTree.file.readBlock(block, 0);
            //////////////////////////////////////////////////////

            n = getNoEntries();

            for (i = 1; i < n; i++)
            // test if the circle intersects the MBR of the entries one by one
            {

                //Console.WriteLine("d :" + entries[i].minDist(center.data).ToString());
                if (Math.Pow(radius, 2) - Math.Pow(entries[i].minDist(center.data), 2) >= (float)1.0e-8)
                {
                    succ = entries[i].getSon();
                    ((INode)succ).rangeQuery(center, radius, res);
                }

                //if (Math.Pow(entries[i].minDist(center.data), 2) <= (float)1.0)
                //{
                //    succ = entries[i].getSon();
                //    ((INode)succ).rangeQuery(center, radius, res);
                //}

            }

       
        }

        /*
        * store in res the mbrs under this node that intersect the query ring
        */
        public void ringQuery(STSPoint center, float radius1, float radius2, SortedLinList res)
        {
            int i, n;
            Boolean s;
            STSNode succ;

            //  #ifdef ZAEHLER
            //page_access += myTree.node_weight[level];
            //  #endif

            myTree.page_access++;

            n = getNoEntries();
            for (i = 0; i < n; i++)
            // test if the circle intersects the MBR of the entries one by one
            {
                s = entries[i].isRingInterSection(center, radius1, radius2);
                if (s)
                {
                    // if c intersects mbr of entry i, follow that node
                    succ = entries[i].getSon();
                    ((INode)succ).ringQuery(center, radius1, radius2, res);
                }
            }
        }




        /*
        * store in Nearest the mbr under this node nearest to the query point
        */
        public void nearestNeighborSearch(STSPoint QueryPoint, STSPoint Nearest, float/*[]*/ nearest_distance)
        {
            float minmax_distance;        // Array fuer MINMAXDIST aller Eintr"age
            int indexliste;        // Liste (for Sorting and Prunching)
            int i, j, k, last, n;
            float akt_min_dist;        // minimal distance computed upto now
            float minmaxdist, mindist;

            BranchList[] activebranchList;

            //#ifdef ZAEHLER
            //    page_access += myTree.node_weight[level];
            //#endif

            n = getNoEntries();

            activebranchList = new BranchList[n]; // Array erzeugen mit n Elementen

            for (i = 0; i < n; i++)
            {
                activebranchList[i].entry_number = i;
                activebranchList[i].minmaxdist = Utilities.MINMAXDIST(QueryPoint, entries[i].bounces, length);
                activebranchList[i].mindist = Utilities.MINDIST(QueryPoint, entries[i].bounces,length);
            }

            // sort branchList
            Utilities.quickSort(activebranchList, 0, activebranchList.Length - 1, Constants.SORT_MINDIST);

            // prune BranchList
            last = Utilities.pruneBranchList(nearest_distance, activebranchList, n);

            for (i = 0; i < last; i++)
            {
                ((INode)entries[activebranchList[i].entry_number].getSon()).nearestNeighborSearch(QueryPoint, Nearest, nearest_distance);

                last = Utilities.pruneBranchList(nearest_distance, activebranchList, last);
            }

            //delete [] activebranchList;
        }

        /*
          * store in res the mbrs under this node nearest to the query point
          */
        public void nearestNeighborSearch(STSPoint QueryPoint,
                        SortedLinList res,
                    float nearest_distance/*[]*/)
        {
            float minmax_distance;        // Array fuer MINMAXDIST aller Eintr"age
            int indexliste;        // Liste (for Sorting and Prunching)
            int i, j, k, last, n;
            float akt_min_dist;        // minimal distance computed upto now
            float minmaxdist, mindist;

            BranchList[] activebranchList;

            //#ifdef ZAEHLER
            //    page_access += myTree.node_weight[level];
            //#endif

            n = getNoEntries();

            k = res.getNoOfElements();     // wird haben eine k-nearest-Narbor-Query

            nearest_distance/*[0]*/ = ((STSData)res.get(k - 1)).distance;  // der aktuell letzte
            // n"achste Nachbar wird
            // versucht zu ersetzen.

            activebranchList = new BranchList[n]; // Array erzeugen mit n Elementen

            for (i = 0; i < n; i++)
            {
                activebranchList[i].entry_number = i;
                activebranchList[i].minmaxdist = Utilities.MINMAXDIST(QueryPoint, entries[i].bounces,length);
                activebranchList[i].mindist = Utilities.MINDIST(QueryPoint, entries[i].bounces,length);
            }

            // sortbranchList
            Utilities.quickSort(activebranchList, 0, activebranchList.Length - 1, Constants.SORT_MINDIST);

            // pruneBranchList
            last = Utilities.pruneBranchList(nearest_distance, activebranchList, n);

            for (i = 0; i < last; i++)
            {
                ((INode)entries[activebranchList[i].entry_number].getSon()).nearestNeighborSearch(QueryPoint, res, nearest_distance);

                last = Utilities.pruneBranchList(nearest_distance, activebranchList, last);
            }

            //delete [] activebranchList;
        }

        /*
        * store in res the mbrs under this node inside the scope of the
        * parameters
        */
        public void range_nnQuery(char[] mbr, SortedLinList res,
                    STSPoint center, float nearest_distance,
                    STSPoint Nearest, bool success)
        {
            float minmax_distance;        // Array fuer MINMAXDIST aller Eintr"age
            int indexliste;        // Liste (for Sorting and Prunching)
            int i, j, k, last, n;
            float akt_min_dist;        // minimal distance computed upto now
            float minmaxdist, mindist;
            int s;

            BranchList[] activebranchList, sectionList;

            if (success)
            {
                rangeQuery(mbr, res);
                return;
            }

            //#ifdef ZAEHLER
            //    page_access += myTree.node_weight[level];
            //#endif



            n = getNoEntries();

            sectionList = new BranchList[n];

            // Erst einmal feststellen, welche der Eintr"age einen Schnitt mit dem
            // aktuellen mbr haben und Ergebnis in sectionList speichern

            for (i = 0; i < n; i++)
            // teste alle Rechtecke auf Ueberschneidung
            {
                s = entries[i].interSection(mbr);
                sectionList[i].entry_number = i;
                if (s == Constants.INSIDE || s == Constants.OVERLAP)
                    sectionList[i].section = true;
                else
                    sectionList[i].section = false;
            }


            activebranchList = new BranchList[n]; // Array erzeugen mit n Elementen

            for (i = 0; i < n; i++)
            {
                activebranchList[i].entry_number = i;
                activebranchList[i].minmaxdist = Utilities.MINMAXDIST(center, entries[i].bounces,length);
                activebranchList[i].mindist = Utilities.MINDIST(center, entries[i].bounces,length);
            }

            // sortbranchList
            //qsort(activebranchList,n,sizeof(BranchList),sortmindist);

            // pruneBranchList
            last = Utilities.pruneBranchList(nearest_distance, activebranchList, n);

            // jetzt nachsehen, ob auch Schnittmenge mit mbr abgeschnitten wurde:
            // falls ja: Schnitt wieder R"ueckg"angig machen

            last = Utilities.testBranchList(activebranchList, sectionList, n, last);

            for (i = 0; i < last; i++)
            {
                ((INode)entries[activebranchList[i].entry_number].getSon()).range_nnQuery(mbr, res, center, nearest_distance,
                      Nearest, success);

                last = Utilities.pruneBranchList(nearest_distance, activebranchList, last);
                last = Utilities.testBranchList(activebranchList, sectionList, n, last);
            }

            //delete [] activebranchList;
            //delete [] sectionList;
        }

        public void overlapping(char[] p, int[] nodes_t)
        {
            int i, n;
            STSNode succ;

            // ein Knoten mehr besucht
            nodes_t[level]++;

            n = getNoEntries();
            for (i = 0; i < n; i++)
            // teste alle Rechtecke auf Ueberschneidung
            {
                if (entries[i].isInside(p))
                {
                    // Rechteck ist interessant -. rekursiv weiter
                    succ = entries[i].getSon();
                    ((INode)succ).overlapping(p, nodes_t);
                }
            }
        }

        // see RTree.nodes()
        public void nodes(int[] nodes_a)
        {
            int i, n;
            STSNode succ;

            // ein Knoten mehr besucht
            nodes_a[level]++;

            n = getNoEntries();
            for (i = 0; i < n; i++)
            // teste alle Rechtecke auf Ueberschneidung
            {
                succ = entries[i].getSon();
                ((INode)succ).nodes(nodes_a);
            }
        }

        /*
        void STSDirNode<Data>::writeinfo(FILE *f)
        {
            int i,j,n;

            float *mbr;

            mbr = get_mbr();
            fprintf(f,"%d\n",level+1);
            fprintf(f,"move %f %f\n",mbr[0],mbr[2]);
            fprintf(f,"draw %f %f\n",mbr[1],mbr[2]);
            fprintf(f,"draw %f %f\n",mbr[1],mbr[3]);
            fprintf(f,"draw %f %f\n",mbr[0],mbr[3]);
            fprintf(f,"draw %f %f\n",mbr[0],mbr[2]);
            fprintf(f,"\n");
            delete [] mbr;

            n = getNoEntries();
            for( i = 0; i < n ; i++)
            entries[i].getSon().writeinfo(f);

        }

        */

        public void delete()
        {
            if (dirty)
            {
                byte[] b = new byte[myTree.file.getBlocklength()];
                try
                {
                    writeToBuffer(b);
                    myTree.file.writeBlock(b, block);
                }
                catch (IOException e)
                {
                    Utilities.processError("STSDirNode delete: Error in writing block", true);
                }
            }
            for (int i = 0; i < noEntries; i++)
            {
                entries[i].delete();
            }
        }

        /*
        protected void finalize()
        {
            if (dirty)
            {
                byte b[] = new byte[myTree.file.getBlocklength()];
                try
                {
                    write_to_buffer(b);
                    myTree.file.write_block(b,block);
                }
                catch (IOException e)
                {
                    Constants.error("STSDirNode finalize: Error in writing block", true);
                }
            }
        }*/

        /*  public void constraints_query(rectangle rect, double distance[], short direction, short MBRtopo, short topology, SortedLinList res)
          {
              int i, n;
              boolean s;
              STSNode succ;

            //  #ifdef ZAEHLER
              //page_access += myTree.node_weight[level];
            //  #endif

              myTree.page_access++;
        
              n = getNoEntries();
              for (i = 0; i < n; i++)
              // test if the circle intersects the MBR of the entries one by one
              {
                  rectangle mbr = Constants.toRectangle(entries[i].bounces);
            
                  //check MBR topological constraints
                  byte rel = relationSet.topoMapping(relation.topological(mbr, rect));
                  int relation_match = relationSet.p2(rel) & MBRtopo;
                  if (relation_match == 0) continue; // disqualified
            
                  //check directional constraints
                  //calculate rect's centroid
                  int center[] = new int[2];
                  center[0] = (rect.UX+rect.LX)/2;
                  center[1] = (rect.UY+rect.LY)/2;
            
                  // if direction constraints do not include some of {E,NE,N,NW,W} = bin(31)
                  // and the mbr's south bound is on the north of the centroid
                  // exclude the entry
                  if (((direction & 31) == 0) && (mbr.UY<=center[1])) continue;
                  // if direction constraints do not include some of {N,NW,W,SW,S} = bin(124)
                  // and the mbr's east bound is on the west of the centroid
                  // exclude the entry
                  if (((direction & 124) == 0) && (mbr.UX<=center[0])) continue;
                  // if direction constraints do not include some of {W,SW,S,SE,E} = bin(241)
                  // and the mbr's north bound is on the south of the centroid
                  // exclude the entry
                  if (((direction & 241) == 0) && (mbr.LY>=center[1])) continue;
                  // if direction constraints do not include some of {S,SE,E,NE,N} = bin(199)
                  // and the mbr's west bound is on the east of the centroid
                  // exclude the entry
                  if (((direction & 199) == 0) && (mbr.LX>=center[0])) continue;
            
                  //check distance constraints
                  //convert center array to STSPoint
                  STSPoint p = new STSPoint(2);
                  p.data[0] = (float) center[0];
                  p.data[1] = (float) center[1];
            
                  s = entries[i].section_ring(p, (float)distance[0], (float)distance[1]);
                  // does the mbr intersect the ring defined by distance array?
                  if (s)
                  {
                      // if c intersects mbr of entry i, follow that node
                      succ = entries[i].getSon();
                      ((Node)succ).constraints_query(rect, distance, direction, MBRtopo, topology, res);
                  }
              }
          }*/
    }
}
